索引
索引出现的目的就是为了提高数据查询的效率,类似于字典的目录。
实现索引有多种方式(索引模型)。常见的有三种:哈希表、有序数组、搜索树。
哈希表
哈希表是一种以键-值(key-value)存储数据的结构,只要输入待查找的key就可以找到其对应的value。
哈希的思路很简单,把值放在数组里,用一个哈希函数吧key换算成一个确定的位置,然后把value放在数组的这个位置上。
如果出现多个key经过哈希换算后得到同一个值,为了处理这种情况,需要拉出一个链表。
因为哈希表并不强制要求索引的值是有序的,因此使用哈希索引做区间查询速度是很慢的。
因此哈希表结构适用于等值查询的场景,比如memcached和一些nosql引擎。、
有序数组
有序数组在等值查询和范围查询中的性能就都很优秀。
但是在更新数据的时候,由于所有的数据都是有序的,所以当插入一条数据的时候,就必须挪动其后所有的记录,成本非常高。
所以,有序数组索引只适用于静态存储引擎,比如按日统计数据,之前不会再有新的数据插入。
搜索树
二叉搜索树的特点在于:每个节点的左子节点小于父节点,父节点又小于右子节点。时间复杂度是O(log(N))。
为了维持O(log(N))的查询复杂度,就需要保证这棵树是平衡二叉树。为了做这个保证,更新的事件复杂度也是O(log(N))。
多叉树就是每个节点有多个子节点,子节点之间保证从左到右依次递增。
二叉树是搜索效率最高的,但是实际上大多数数据库存储都不会使用二叉树,因为索引不止存在于内存中,还得写在磁盘上。
假设一颗100w节点的平衡二叉树,树高20。一次查询需要访问20个数据模块。假设机械硬盘读取一个模块需要10ms,那么查询一次就需要200ms。
为了让一个查询尽量少读磁盘,就必须让查询过程中尽量少访问数据块。因此多叉树是最好的选择。
InnoDB的索引模型
在InnoDB中,表都是根据主键顺序以索引的形式存放的,这种存储方式的表称之为索引组织表。
InnoDB使用B+树索引模型。每个索引在InnoDB里面对应一颗B+树。
主键索引的叶子节点存的是整行数据,也称之为聚簇索引(clustered index)。根据主键索引进行查询,只需要查询主键的B+树。
非主键索引的叶子内容是主键索引的值,也称之为二级索引(secondary index)。根据非主键索引进行查询,需要先查询非主键索引B+树得到主键的值,然后再查询主键索引的B+树。这个过程称之为回表。
基于非主键索引的查询需要多扫描一颗索引树。因此在查询中尽量使用主键查询。
索引维护
B+数为了维护索引有序性,需要在插入新值的时候根据索引的大小挪动其之后的数据,空出位置。
如果需要变动的数据页已满,这时候就需要申请一个新的数据页,然后挪动不分数据过去,称之为页分裂。页分裂除了影响性能,还影响数据页的利用率。原本放在一页的数据分到了两页中,整体空间占用率降低了大约50%。
当两个相邻的页由于删除了数据,利用率很低之后,就会进行数据页合并。合并的过程相当于分裂的逆过程。
因此建议在绝大多数情况下使用自增索引(根据实际情况选择)。 NOT NULL PRIMARY KEY AUTO_INCREMENT
。
覆盖索引
mysql> create table T (
id int primary key,
k int NOT NULL DEFAULT 0,
v varchar(255) NOT NULL DEFAULT '',
index k(k)
) engine=InnoDB;
select * from T where k between 1 and 3;
当执行这条sql查询的时候
1. 在k索引树上找到k=1的记录,获取其对应主键id = 1
2. 在id索引树上找到id=1的数据行
3. 在k索引树上找到k=2的记录,获取其对应主键id = 2
4. 在id索引树上找到id=1的数据行
5. 在k索引树上找到k=3的记录,假设没找到,循环结束。
在这个查询过程中,每次为了获得行数据,需要先拿到主键id然后再主键索引树上进行行查询。这个行为称之为回表。
但是如果是使用以下语句
select id from T where k between 1 and 3;
因为所需要返回的值id,就在k的索引树上,则不需要回到id索引树上进行查询行数据。由于减少了树的搜索次数,可以显著的提升查询性能。这样的操作称之为索引覆盖。
假设有需求需要高频的根据k查询v,这时候建立联合索引就可以实现索引覆盖。
当然,为了实现索引覆盖,就要承担索引字段冗余问题的维护,这点需要注意一下。
左前缀原则
索引项是按照索引定义里出现的字段顺序进行排序的。
假如你使用like语句进行查询,使用 where k like 'a%'
,这时依旧可以命中索引。
所以当有了(a,b)这个联合索引之后,一般就不需要单独建a索引。
索引下推
mysql5.6引入了索引下推优化(index condition pushdown),可以再索引遍历过程中对索引中包含的字段先做判断,直接过滤掉不满足条件的记录。从而避免反复回表的情况。
额外
通过 alter table T engine=InnoDB 来重建索引